
from Code_Link_02 import ListNode
from Code_Link_02 import printLink

''' 交换相邻的节点
1->2->3->4->5
2->1->4->3->5
'''
def l24(head:ListNode):
    if head == None:return []
    pre = head
    if head.next == None:return head
    cur = head.next
    res = head.next

    pre_tmp = None #连接第二轮循环的第一个节点与第一轮循环的第二个节点
    while pre:

        if pre_tmp:# 第二轮循环 2->1(pre_tmp) 4(cur)->3(pre)
            if cur == None:break
            pre_tmp.next = cur #记录翻转后的最后一个节点，用于和后面循环的节点连接
            pre_tmp = pre
            pass
        else:pre_tmp = pre
        tmp = cur.next  # tmp = 3
        cur.next = pre #翻转1 -> 2 => 2- > 1(pre)  2->1 3->4

        pre.next = tmp # 2(cur)-> 1(pre_tmp)-> 3(tmp) ->4
        pre = tmp     # 2(cur)->1(pre_tmp) ->3(pre,tmp) ->4
        if pre:cur = pre.next # 2->1->3(pre,tmp)->4(cur) 完成一轮翻转
    #printLink(res)
    return res
    pass

'''
1->2->3->4 
需要考虑cur指针和cur.next指针指向正确位置，注意步骤2 步骤4中cur及cur.next指针
null(cur) -> 1(t1) -> 2(t2) -> 3 -> 4 -> 5 -> 6
null(cur)    1 <- 2    3 -> 4  步骤1 1 2 反转 
cur -> 2 -> 1   3 -> 4  步骤2 cur.next = 2
cur -> 2(t2) -> 1(t1) -> 3 -> 4  步骤3 1->3
2 -> 1(cur) -> 3 -> 4 步骤4 cur = 1

2 -> 1(cur) -> 3 -> 4 -> 5 -> 6
2 -> 1(cur) 4 -> 3   5 -> 6     步骤1 3 4反转
2 -> 1(cur) -> 4 -> 3   5 -> 6 步骤2 cur.next = 4
2 -> 1(cur) -> 4 -> 3  -> 5 -> 6  步骤3 3->后面节点
2 -> 1 -> 4 -> 3(cur) ->5 ->6(cur) 步骤4 cur = 3

'''
def l24_1(head:ListNode):
    dummy_head = ListNode(next=head) #虚拟头节点
    cur = dummy_head
    while cur.next and cur.next.next:
        tmp1 = cur.next # tmp1 1
        tmp2 = cur.next.next # tmp2 2
        tmp3 = cur.next.next.next # tmp3 3
        tmp2.next = tmp1 #步骤1 2->1-<cur(空)
        cur.next = tmp2 #步骤2 cur(dump) -> 2 -> 1 3-> 4 此时虚拟头节点指向了2，cur释放出来用于步骤4
        tmp1.next = tmp3 #步骤3 dump -> 2 -> 1 ->3 -> 4
        cur = tmp1 #步骤4 dump -> 2 -> 1(cur) -> 3 -> 4
        #printLink(dummy_head.next)

    return dummy_head.next
    pass

if __name__ == '__main__':
    link7 = ListNode(7)
    link6 = ListNode(6,link7)
    link5 = ListNode(5,link6)
    #link5 = ListNode(5)
    #link4 = ListNode(4,link5)
    link4 = ListNode(4)
    link3 = ListNode(3,link4)
    #link3 = ListNode(3)
    link2 = ListNode(2,link3)
    link1 = ListNode(1,link2)
    #printLink(link1)
    res = l24_1(link1)
    printLink(res)

    #l206(link6)
    pass